#include <cstdlib>
#include <iostream>
#include <vector>
#include <sstream>
#include <fstream>

#define couleur(param) printf("\033[%sm",param)

using namespace std;

void graphRand(unsigned int n, unsigned int m, unsigned int (*edge)[2]);
std::string DrawGraph(unsigned int n, unsigned int m, unsigned int edge[][2]);
void composantes (unsigned int n, unsigned int m, unsigned int edge[][2], unsigned int comp[]);
void ecrituretailles (unsigned int n, unsigned int m, unsigned int comp[]);
void afficheedge (unsigned int m, unsigned int edge[][2]);
void affichecomp (unsigned int n, unsigned int comp[]);

int main()
{
	srand (time(NULL));

	unsigned int n;     // Nombre de sommets.	
	unsigned int m;     // Nombre d'aretes.	
	couleur("33");
	std::cout << "Entrer le nombre de sommets : ";	
	couleur("0");
	std::cin >> n;	
	couleur("33");
	std::cout << "Entrer le nombre d'aretes : ";	
	couleur("0");
	std::cin >> m;

	unsigned int (*edge)[2] = new unsigned int[m][2];    // Tableau des aretes.
	unsigned int* comp = new unsigned int[n];       // comp[i] est le numero de la composante contenant i.

	graphRand(n, m, edge);
/*
	couleur("31");
	std::cout << std::endl << "--- Liste des sommets ---" << std::endl;
	couleur("0");
	std::cout << "{";
	for (unsigned int i(0); i < n; i++)
	{
		std::cout << i << ", ";
	}
	std::cout << "\b\b}" << std::endl;

	couleur("31");
	std::cout << std::endl << "--- Liste des aretes ---" << std::endl;
	couleur("0");
	afficheedge(m, edge);

*/

	std::cout << "tt";

	composantes(n, m, edge, comp);
/*
	couleur("31");
	std::cout << std::endl << "--- Affichage des composantes apres l'algorithme composantes ---" << std::endl;
	couleur("0");
	affichecomp(n, comp);
*/
	ecrituretailles(n, m, comp);
	
	/**
	g++ AB.cpp -o AB
	AB > arbo.tex
	pdflatex arbo.tex
	arbo.pdf
	*/

/*
	std::ofstream file;
	file.open("graph.tex");

	file << DrawGraph(n, m, edge);
*/


	//file << "te";
	
	//delete edge[2];
	//delete comp;

	return 0;
}

void graphRand(unsigned int n, unsigned int m, unsigned int (*edge)[2])
{
	srand(time(NULL));

	for(unsigned int i(0); i<m; i++)
	{
		edge[i][0] = rand() % n;
		edge[i][1] = rand() % n;
	}
	
}


std::string DrawGraph(unsigned int n, unsigned int m, unsigned int edge[][2])
{
	std::string sortie;
	
	srand(time(NULL));

	int k(0);
	
	for(unsigned int i(0); i<n; i++)
	{
		std::ostringstream oNum, oLign, oCol;
	
		oNum << i;
		oLign << (i % 8) * 2;
		oCol << (i + k%7 + rand() % 2) % 23;
		sortie += "\\node[draw] (SZ"+oNum.str()+") at ("+oLign.str()+", "+oCol.str()+") { "+oNum.str()+"};\n";

		k += 3;
	}
	
	for(unsigned int i(0); i<m; i++)
	{
		std::ostringstream oLign, oCol;
	
		oLign << edge[i][0];
		oCol << edge[i][1];
		sortie += "\\draw (SZ"+oLign.str()+") -- (SZ"+oCol.str()+");\n";
	}
	
	sortie = "\\documentclass[a4paper]{article} \n \\usepackage{tikz} \n \\begin{document} \n \\begin{tikzpicture}\n" + sortie + "\n  \\end{tikzpicture}\n  \\end{document} \n";
	
	return sortie;
}



void composantes (unsigned int n, unsigned int m, unsigned int edge[][2], unsigned int comp[])
{
	for (unsigned int i(0); i < n; i++)
	{
		comp[i] = i;
	}

	/**
	* NON OPTIMISEE (avant EXO4)
	*/
	/*
	for (unsigned int i(0); i < m; i++)
	{
		if (comp[edge[i][0]] != comp[edge[i][1]])
		{
			unsigned int aux(comp[edge[i][0]]);
			for (unsigned int j(0); j < m; j++)
			{
				if (comp[edge[j][0]] == aux)
					comp[edge[j][0]] = comp[edge[i][1]];

				if (comp[edge[j][1]] == aux)
					comp[edge[j][1]] = comp[edge[i][1]];
			}
		}
	}*/
	/**
	* OPTIMISEE (apres EXO4)
	*/
	for (unsigned int i(0); i < m; i++)
	{
		if (comp[edge[i][0]] != comp[edge[i][1]])
		{
			unsigned int aux(0), x(0);
			if (comp[edge[i][0]] > comp[edge[i][1]])
			{
				aux = comp[edge[i][0]];
				x=1;
			}
			else
			{
				aux = comp[edge[i][1]];
				x=0;
			}

			for (unsigned int j(0); j < m; j++)
			{

				if (comp[edge[j][0]] == aux)
					comp[edge[j][0]] = comp[edge[i][x]];

				if (comp[edge[j][1]] == aux)
					comp[edge[j][1]] = comp[edge[i][x]];
			}
		}
	}
}

void ecrituretailles (unsigned int n, unsigned int m, unsigned int comp[])
{
	int *csize = new int [n];

	for (unsigned int i(0); i < n; i++)
	{
		csize[i] = 0;
	}

	for (unsigned int i(0); i < n; i++)
	{
		csize[comp[i]]++;
	}

	int *nbComp = new int [n];

	for (unsigned int i(0); i < n; i++)
	{
		nbComp[i] = 0;
	}

	for (unsigned int i(0); i < n; i++)
	{
		nbComp[csize[i]]++;
	}

	couleur("33");
	std::cout << std::endl << "Nombre de points isoles du graphe : " << nbComp[1] << "." << std::endl;
	couleur("0");

	for (unsigned int i(2); i <= n; i++)
	{
		if (nbComp[i] != 0)
		{
			couleur("33");
			std::cout << "Il y a " << nbComp[i] << " composantes de taille " << i << "." << std::endl;
			couleur("0");
		}
	}
}

void afficheedge (unsigned int m, unsigned int edge[][2])
{
	for (unsigned int i(0); i < m; i++)
	{
		std::cout << "Arete n°" << i << " - [" << edge[i][0] << ", " << edge[i][1] << "]" << std::endl;
	}

}

void affichecomp (unsigned int n, unsigned int comp[])
{
	for (unsigned int i(0); i < n; i++)
	{
		std::cout << "comp [" << i << "] = " << comp[i] << std::endl;
	}
}




